package java_thinking.unit_17;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @Desc:
 *      必看:   https://blog.csdn.net/world6/article/details/70053356
 *              https://blog.csdn.net/panweiwei1994/article/details/77667054
 *      1.HashMap 的实例有两个参数影响其性能：
 *          1.1 初始容量:容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量
 *          1.2 加载因子:加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容
 *              量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数;
 *              通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本
 *      2.HashMap 大概具有以下特点：
 *          2.1 底层实现是 链表数组，JDK 8 后又加了 红黑树
 *          2.2 实现了 Map 全部的方法
 *          2.3 key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
 *          2.4 允许空键和空值（但空键只有一个，且放在第一位）
 *          2.5 元素是无序的，而且顺序会不定时改变
 *          2.6 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
 *          2.7 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
 *          2.8 两个关键因子：初始容量、加载因子
 *
 *      3.初始容量为 16，加载因子为 0.75
 *      4.总结插入逻辑如下：
 *          4.1 先调用 hash() 方法计算哈希值
 *          4.2 然后调用 putVal() 方法中根据哈希值进行相关操作
 *          4.3 如果当前 哈希表内容为空，新建一个哈希表
 *          4.4 如果要插入的桶中没有元素，新建个节点并放进去
 *          4.5 否则从桶中第一个元素开始查找哈希值对应位置
 *               4.5.1 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找
 *               4.5.2 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入
 *               4.5.3 否则还是从传统的链表数组中查找、替换，结束查找
 *               4.5.4 当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化
 *          4.6 最后检查是否需要扩容
 *
 *      5.hash()大概意思就是：
 *          由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此
 *          1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或，这样可以避免只靠低位数据来计算哈希时
 *          导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀
 *          什么是hash见java_thinking.unit_17.WhatIsHash
 *
 *      6.resize()扩容过程中几个关键的点：
 *          1.新初始化哈希表时，容量为默认容量，阈值为 容量*加载因子
 *          2.已有哈希表扩容时，容量、阈值均翻倍
 *          3.如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构
 *          4复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是
 *              e.hash & (newCap - 1)，等价于 e.hash % newCap
 *          5.结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。
 *          6.所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize()。
 *
 *      7.查找 方法比较简单:
 *          1.先计算哈希值;
 *          2.然后再用 (n - 1) & hash 计算出桶的位置;
 *          3.在桶里的链表进行遍历查找。
 *
 *          时间复杂度一般跟链表长度有关，因此哈希算法越好，元素分布越均匀，get() 方法就越快，不然遍历一条长链表，太慢了。
 *          不过在 JDK 1.8 以后 HashMap 新增了红黑树节点，优化这种极端情况下的性能问题
 *      8.面试问题见java_thinking/unit_17/ContainerTheory.java:22
 *      http://www.importnew.com/31278.html
 *
 *      9.为什么要用红黑树/为什么长度超过8时候要改为红黑树：
 *          9.1 如果元素小于8个，查询成本高，新增成本低
 *          9.2 如果元素大于8个，查询成本低，新增成本高
 *
 *      10.红黑树概念与二叉搜索树：
 *          红黑树是一种自平衡二叉查找树,平衡的最终目的是为了“平衡”，让树的左右子树高度保持在一个相对平衡的状态
 *          二叉搜索树的规则是：任何节点的键值一定大于其左子树的每一个节点值，并小于右子树的每一个节点值
 *
 *      11.红黑树的定义也是它的性质，有以下五条:
 *          1. 节点是红色或黑色
 *          2. 根是黑色
 *          3. 所有叶子都是黑色（叶子是NIL节点）
 *          4. 如果一个节点是红的，则它的两个儿子都是黑的
 *          5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点
 *
 *      12.拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树：
 *          之所以选择红黑树是为了解决二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构，遍历查找会非常慢；而红黑树在
 *          插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题。
 *          我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长
 *          度大于8的时候，会使用红黑树；如果链表长度很短(6)的话，根本不需要引入红黑树，引入反而会慢
 *
 *      13.HashMap专门预留给LinkedHashMap 的afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 方法；
 * @author: cww
 * @DateTime: 2019-05-04 10:22
 */

public class HashMapTheory<K,V> {


    public static void main(String[] args) {
        Map<String,Integer> integerMap = new HashMap<>(16);
        integerMap.put("first",10);
        integerMap.put("first",17);
        System.out.println(" f ");
        Set<Map.Entry<String, Integer>> set = integerMap.entrySet();
        Iterator<Map.Entry<String, Integer>> it = set.iterator();
        while(it.hasNext()) {
            Map.Entry<String, Integer> m = it.next();
            m.getKey();
            m.getValue();
        }

        for (Map.Entry<String, Integer> map: integerMap.entrySet()) {

        }
    }
}
